1. 题目

给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。

求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。

说明: 请尽可能地优化你算法的时间和空间复杂度。

示例 1: 输入: nums1 = [3, 4, 6, 5] nums2 = [9, 1, 2, 5, 8, 3] k = 5 输出: [9, 8, 6, 5, 3]

示例 2: 输入: nums1 = [6, 7] nums2 = [6, 0, 4] k = 5 输出: [6, 7, 6, 0, 4]

示例 3: 输入: nums1 = [3, 9] nums2 = [8, 9] k = 3 输出: [9, 8, 9]

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/create-maximum-number 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题思路

2.1. 定义子问题

给定一个以数组表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最大。（可参考402 移掉k位数字）

对于num[i+1]，若num[i+1]>num[i]，则移除掉num[i]。否则暂时保留。直至移掉k位数字。不足则从末位移除补齐。

借助栈的思想：

vector<int> removeKNumber(vector<int>& num, int k){
    vector<int> stack;
    int len = num.size();
    for(int i=0;i<len;++i){
        while(!stack.empty() && num[i]>stack.back() && k){
            k--;
            stack.pop_back();
        }
        stack.push_back(num[i]);
    }
    while(k--) stack.pop_back();
    return stack;
}

2.2. 合并子问题

分别得到两个数组中的最大数字后，将两个合并。

两个指针分别指向数组num1和num2的头，每次选数字大的，若是两个数字相等，则需要依次往后比较直至出现不同的数字（这里用\里的lexicographical_compare函数简化代码，即比较字典序）。

vector<int> mergeTwoNums(vector<int>& num1, vector<int>& num2){
    vector<int> ans;
    auto p1=num1.begin(), p2 = num2.begin();
    while(p1!=num1.end() && p2!=num2.end()){
        if(*p1 > *p2) ans.push_back(*p1),p1++;
        else if(*p1 < *p2) ans.push_back(*p2),p2++;
        else {
            if(lexicographical_compare(p1,num1.end(),p2,num2.end())) 
                ans.push_back(*p2),p2++;
            else ans.push_back(*p1),p1++;
        }
    }
    while(p1!=num1.end()) ans.push_back(*p1),p1++;
    while(p2!=num2.end()) ans.push_back(*p2),p2++;
    return ans;
}

2.3. 求解

总共要选取k个数字构成最大数，考虑从数组nums1中取出数字的个数范围[low,high]，求出每种情况下的最大值。最后取总的最大值即可。

3. 代码

class Solution {
public:
    vector<int> removeKNumber(vector<int>& num, int k){
        vector<int> stack;
        int len = num.size();
        for(int i=0;i<len;++i){
            while(!stack.empty() && num[i]>stack.back() && k){
                k--;
                stack.pop_back();
            }
            stack.push_back(num[i]);
        }
        while(k--) stack.pop_back();
        return stack;
    }
    vector<int> mergeTwoNums(vector<int>& num1, vector<int>& num2){
        vector<int> ans;
        auto p1=num1.begin(), p2 = num2.begin();
        while(p1!=num1.end() && p2!=num2.end()){
            if(*p1 > *p2) ans.push_back(*p1),p1++;
            else if(*p1 < *p2) ans.push_back(*p2),p2++;
            else {
                if(lexicographical_compare(p1,num1.end(),p2,num2.end())) 
                    ans.push_back(*p2),p2++;
                else ans.push_back(*p1),p1++;
            }
        }
        while(p1!=num1.end()) ans.push_back(*p1),p1++;
        while(p2!=num2.end()) ans.push_back(*p2),p2++;
        return ans;
    }
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        int low = nums2.size()>k?0:k-nums2.size();
        int high = nums1.size()>k?k:nums1.size();
        vector<int> maxNums1,maxNums2,res(k,0),tmp;

        for(int i=low;i<=high;++i){//枚举从nums1中选出i个数字，则nums2中选出k-i个
            maxNums1 = removeKNumber(nums1, nums1.size()-i);
            maxNums2 = removeKNumber(nums2, nums2.size()-k+i);
            tmp = mergeTwoNums(maxNums1, maxNums2);
            if(lexicographical_compare(res.begin(), res.end(), tmp.begin(), tmp.end())) 
                res.assign(tmp.begin(), tmp.end()); 
        }
        return res;
    }
};